class Solution(object):
    def numWays(self, s):
        n = len(s)
        prefix = [0] * n
        if s[0] == '1':
            prefix[0] = 1
        for i in range(1, n):
            prefix[i] = prefix[i - 1] + int(s[i] == '1')
        if prefix[-1] % 3 != 0:
            return 0
        if prefix[-1] == 0:
            return (n - 1) * (n - 2) // 2 % (10 ** 9 + 7)
        target1 = prefix[-1] // 3
        c1 = 0
        target2 = target1 * 2
        c2 = 0
        for i in range(n):
            if prefix[i] == target1:
                c1 += 1
            if prefix[i] == target2:
                c2 += 1
        return c1 * c2 % (10 ** 9 + 7)